﻿//Write a program that reads two integer numbers N and K and an array of N elements from the console.
//Find in the array those K elements that have maximal sum.


using System;
using System.Collections.Generic;

public class ArrayElementsWithMaximalSum
{
    public static void Main()
    {
        Console.Write("Enter first integer N = ");
        int integerN = int.Parse(Console.ReadLine());
        Console.Write("Enter second integer K = ");
        int integerK = int.Parse(Console.ReadLine());
        Console.WriteLine("Enter {0} elements of the array", integerN);
        int[] array = new int[integerN];
        for (int i = 0; i < integerN; i++)
        {
            array[i] = int.Parse(Console.ReadLine());
        }
        Console.WriteLine();
        
        int maxSum = int.MinValue;
        List<int> combinationMaxSum = new List<int>();
        for (int combinationCount = 1; combinationCount < Math.Pow(2, integerN); combinationCount++)
        {
            int sum = 0;
            List<int> combination = new List<int>();
            combination = GetCombination(combinationCount);
            if (combination.Count == integerK)
            {
                for (int j = 0; j < combination.Count; j++)
                {
                    sum += array[combination[j]];
                }
                if (sum > maxSum)
                {
                    maxSum = sum;
                    combinationMaxSum.Clear();
                    combinationMaxSum = combination;                    
                }
            }
        }
        Console.WriteLine("The maximal sum is {0}", maxSum);
        Console.Write("The combinaion is: ");
        Console.Write('{');
        for (int k = 0; k < combinationMaxSum.Count; k++)
        {
            if (k < combinationMaxSum.Count - 1)
            {
                Console.Write("{0}, ", array[combinationMaxSum[k]]);
            }
            else
            {
                Console.Write("{0}", array[combinationMaxSum[k]]);
            }
        }
        Console.Write("}\n");        
    }

    private static List<int> GetCombination(int count)
    {
        string binaryLength = Convert.ToString(count, 2);
        List<int> combination = new List<int>();
        for (int i = 0; i < binaryLength.Length; i++)
        {
            int mask = 1;
            if ((count & mask) == 1)
            {
                combination.Add(i);
            }
            count >>= 1;
        }

        return combination;        
    }
}